package com.study.algorithm.basicalsort.imp;

import com.study.algorithm.basicalsort.BasicalSort;
import com.study.algorithm.utils.ListUtil;

import java.util.List;

/**
 * 冒泡排序
 */
public class BubbleSortImpl implements BasicalSort {


    @Override
    public List<Integer> basicalSort(List<Integer> originList) {
        int size = originList.size();
        List<Integer> destList = ListUtil.DeepClone(originList);
        if (size <= 1) {
            return destList;
        }
        for (int i = 0; i < size; i++) {
            bubbleCurrMaxToCurrBottom(destList, size - i);
        }
        return destList;
    }


    /**
     * 从头部往底部沉（与冒泡顺序相反，从底部往头部冒）
     * 遇到比自己小的就交换位置
     * 然后记当前位置为最大值所在位置
     */
    private void bubbleCurrMaxToCurrBottom(List<Integer> integers, int currSize) {
        if (currSize <= 1) {
            return;
        }
        int maxVal = 0;
        int maxIndex = 0;
        for (int currIndex = 0; currIndex < currSize; currIndex++) {
            int currValue = integers.get(currIndex);
            if (currIndex == 0) {
                maxVal = currValue;
                maxIndex = currIndex;
                continue;
            }
            if (maxVal > currValue) {
                ListUtil.ExchangeValue(integers, maxIndex, currIndex);
            }
            if (maxVal <= currValue) {
                maxVal = currValue;
            }
            maxIndex = currIndex;
        }
    }


}
